package com.ming.learn.from.carl.doublepointer;

import com.ming.commons.utils.ListNode;

/*
第142题.环形链表II
 */
public class Of20201230LeetCode142 {
    /*
    题意：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    如果 pos 是 -1，则在该链表中没有环。
     */
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1,new ListNode(2,new ListNode(3)));
        ListNode listNode2 = new ListNode(4,new ListNode(5,new ListNode(6)));
        listNode1.next.next.next=listNode2;
        listNode2.next.next.next=listNode1.next.next;
        ListNode listNode = detectCycle(listNode1);
        System.out.println(listNode.val);
        int index=0;
        while (listNode1!=listNode){
            listNode1=listNode1.next;
            index++;
        }
        System.out.println(index);
    }

    private static ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode index1 = head;
                ListNode index2 = fast;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}
